/*
date:20210403
key:经典动态规划，注意转移时有斜向右下，因此要有初始行和列为0
*/
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) 
    {
        if(text1.size()==0||text2.size()==0)
        {
            return 0;
        }
        int**M=new int*[text1.size()+1];
        int i,j;
        for(i=0;i<text1.size()+1;i++)
        {
            M[i]=new int[text2.size()+1];
        }
        //第一行和第一列都是0，初始化一下
        for(j=0;j<text1.size()+1;j++)
        {
            M[j][0]=0;
        }
        for(j=0;j<text2.size()+1;j++)
        {
            M[0][j]=0;
        }
        for(i=1;i<text1.size()+1;i++)
        {
            for(j=1;j<text2.size()+1;j++)
            {
                if(text1[i-1]==text2[j-1])
                {
                    M[i][j]=M[i-1][j-1]+1;
                }
                else
                {
                    M[i][j]=(M[i-1][j]>M[i][j-1])?M[i-1][j]:M[i][j-1];
                }
            }
        }
        return M[i-1][j-1];
    }
};